The present invention relates, generally, to the coupling of asynchronous electronic devices, and, in particular embodiments to synchronization of READ/WRITE pointers in a first in first out (xe2x80x9cFIFOxe2x80x9d) queue.
The capability of electronic systems is increasing at a significant rate, as integrated circuit technology improves. The number of transistors which can be placed on an integrated circuit tends to double every 18 months according to a hypothesis which was accurately postulated by Gordon Moore of Intel Corp. over twenty years ago. As more transistors can be integrated into integrated circuits there is a proportional increase in processing power. Because of this increased processing power, applications having data manipulation intensive requirements, as speech recognition, Computer Aided Tomography (CAT) scanning, electronic games and real-time compression of television signals, are now possible.
In particular, the frequency of use and versatility of video data is increasing. For example, video data is used for electronic games, for video teleconferencing systems, for televisions, for Video Cassette Recorders (VCRs), to display movie images on computer monitors and for transmitting moving images via networks such as the internet. Moreover, different video components are often connected together. For example, a video encoder may be connected to a video decoder, and the video encoder and video decoder may transmit data to each other to encode or decode the data respectively.
The connected video components may have different clock rates. The clock rate is the speed at which a digital circuit operates. Every synchronous digital circuit contains one or more internal clocks that regulate the rate at which circuit operations are performed. These internal clocks synchronize the various circuit operations. Different synchronous digital circuits may have differing clock rates, or, even if they are the same clock rate, digital synchronous circuits may have clocks that drift with respect to each other. For example, the microprocessors contained in personal computers may have clock rates anywhere from 4 MHz to over 600 MHz. The faster the clock, the more instructions the microprocessor can execute per second. Clock speeds are generally expressed in megahertz, one megahertz being equal to one million cycles per second.
As data is transmitted from a first component to a second component, the second component may need to synchronize with the data that it is receiving from the first component. For example, a VCR which is recording a video signal on a tape must synchronize itself to the video signal that it is receiving from its tuner. Traditionally circuits containing phase lock loops are used to synchronize a video signal with a display. Another method for synchronizing data between components is by storing the data in a FIFO (First In First Out) queue. A FIFO queue is a data structure used by computing systems that is very similar in concept to the checkout line at a supermarket. Data, like the customers in a checkout line, arrive at the queue and then are taken in turn through the checkout.
In an application that utilizes a FIFO the data that is inserted in a FIFO first will be the first to come out of the queue, hence the designation First In First Out or FIFO. Data arrives in the FIFO and is stored for a period and then is removed, as the receiver of the data is able to accept it. In one scenario a video decoder writes data into a FIFO queue and the video encoder reads that data from the FIFO queue. Data may be written into the FIFO queue by a component with the first clock rate and then the data may be read out of the FIFO queue by a component with a second clock rate. The FIFO queue can be used for synchronization of data across different clock rate domains. The use of a FIFO queue to synchronize data between components of different clock rates has some inherent problems which must be dealt with if reliable operation is to be maintained.
One problem exists because of the different clock rates between the circuits. Because of the different clock rates, it is possible that more data can be written into the FIFO queue than it can hold, causing the FIFO queue to overflow. Overflow can also occur when the second component, which is removing data from the FIFO queue, does not remove data at a fast enough rate so that the data within the FIFO queue reaches a maximum limit. When an overflow condition occurs, some recovery mechanism must be instituted if the circuit is to resume normal operation.
Conversely, it is possible that the write operation will be slower than the read operation. When this condition is present, or if the writing stops into the FIFO queue, an underflow condition may occur. An underflow condition can occur when a circuit calls for data that has not yet been placed into the FIFO queue. In other words, the circuit may call for data that is not in the FIFO queue and hence old data from the queue may be re-read. When an underflow occur, some recovery mechanism must be instituted if the circuit is to resume normal operation. One method of avoiding overflow is to increase the size of the FIFO queue, thereby allowing it to contain more data before it overflows. A second method of attempting to maintain reliable operation between the two circuits is to adjust the clocks within the two circuits so that their frequencies are as close as possible. Neither of these methods are 100% effective. For example, increasing the size of a FIFO may be able to prolong the overflow of data within a FIFO, but it cannot stop the overflow from occurring. Also, in the case where the clocks of these two components have frequencies that are matched, there will still be some difference from the clock in the first component to the clock in the second component unless they are actually locked together. This timing gap will eventually cause an underflow or an overflow condition. In some systems, in addition to increasing the size of the FIFO queue and attempting to lock the clocking signals together, recovery circuits may be used. System designers accept the fact that completely preventing underflow or overflow is difficult and have developed methods to resynchronize the components which have become unsynchronized due to an underflow or overflow in the FIFO queue from which data will be read. In particular, the component that writes to the FIFO queue writes data to the address to which a write pointer points in the FIFO queue, and the component that reads data uses a read pointer, which specifies an address in the FIFO queue. For synchronization, the read and write pointers that point into the FIFO queue are realigned. Some systems perform this synchronization by using a reset control signal which sets both the read and the write pointer back to the address zero of the FIFO queue.
Additionally, some video systems reset a FIFO queue when in a vertical blanking interval (i.e., when no viewable data is being transmitted). Note that blanking refers to the part of a video transmission that has no viewable content, for example, to allow time when the television""s electron gun is moving from the bottom to the top of the screen as it scans images. In many systems, this resetting of the read and write FIFO queue pointers occurs when it is known that no data should be in the queue, such as during a vertical blanking interval. When no data should be in the FIFO queue, both pointers may be reset to the same point, typically a zero address. A FIFO queue must be in a known state to reset both pointers and when the FIFO queue is in an empty state, both read and write pointers may be reset to the same point, indicating that the queue is empty. In some systems, the FIFO queue may not be expected to be empty except during vertical blanking, and read and write pointer synchronization cannot occur except during the vertical blanking period.
Conventional systems, however, do not provide aligning read and write pointers of a IFO queue at any time and at any sequential address. In addition, the requirement that the FIFO queue be in a known state to be reset may allow the FIFO to be reset only during the vertical interval. The ability to align read and write pointers of a FIFO at any time or any sequential address would be especially useful to provide synchronization, where a FIFO queue is used to pass data from a video system having a first clock rate to another video system having a different clock rate.
If a FIFO queue can only be reset during a vertical interval, an entire vertical scan may be disrupted by an overflow or an underflow of the FIFO queue until the FIFO queue can be resynchronized during a vertical blanking period.
Accordingly, to overcome limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading the present specification, preferred embodiments of the present invention relate to the synchronization of components having different clock rate domains and sharing a FIFO queue.
A preferred embodiment of the present system involves an improved technique for synchronizing the read and write pointers using a FIFO queue.
In particular, preferred embodiments of the present system provide a technique for aligning the read and write pointers of a FIFO queue at any data location without requiring the FIFO queue to be empty. This is especially useful to provide synchronization when a FIFO queue is used to pass data from a video system having a first clock rate to another video system having a different clock rate. It, however, can be used to synchronize other asynchronous circuits.
In one preferred embodiment, when an end of line of data that is being written into the FIFO queue is detected, the current address of the FIFO write pointer is stored. When the end of line on the read side is detected, the read pointer is set to the stored write pointer location. This method allows for resynchronization of the FIFO queue on a line by line basis.
Embodiments of the present invention are described herein, in terms of lines of video data. Those skilled in the art will realize that this is by the way of illustration only, as an example likely to be commonly familiar with practitioners in the art. Further embodiments, however, have wide applicability to other forms of synchronization of streams of data. Yet further embodiments have applicability to other techniques within the field of video display, such as the display of one field of data encapsulated within another, such as is present in a picture in picture display on a common television set.